class Test {
    private static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int x) {
            val = x;
        }
    }

    // 记录当前碰到最下边的层的最右节点的值
    private Integer result;
    // result所在的层
    private int resultLevel;

    public int getMostRightBottomNode(Node root) {
        deepestTraverse(root, 0);
        return result;
    }

    public void deepestTraverse(Node node, int level) {
        if (node.left == null && node.right == null) {
            if (result == null) {
                /*
                 如果是叶子节点并且result还没有初始化，
                 则对result和resultLevel赋值（实际就是初始化根节点的值）
                */
                result = node.val;
                resultLevel = level;
            } else if (level > resultLevel) {
                /*
                 如果是叶子节点，并且result已被初始化的情况下，
                 如果当前节点的层级比resultLevel高，
                 则赋值给result和resultlevel（因为每次是先走右节点，因此保证一个层级中，只会记录最右节点）
                 */
                result = node.val;
                resultLevel = level;
            }
        } else {
            // 每次先走有节点，再走左节点
            if (node.right != null) {
                deepestTraverse(node.right, level + 1);
            }
            if (node.left != null) {
                deepestTraverse(node.left, level + 1);
            }
        }
    }
}


